package com.arceus.leetcode;

/**
 * Create by qianxia.zgm  5:06 下午 2020/9/17
 * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
 *
 * 示例1:
 *
 * 输入：n = 3
 * 输出：4
 * 说明: 有四种走法
 * 示例2:
 *
 * 输入：n = 5
 * 输出：13
 * 提示:
 *
 * n范围在[1, 1000000]之间
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/three-steps-problem-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T0801 {

    public static int waysToStep(int n) {

        if(n <= 2) return n;
        if (n == 3) return 4;
        int[] d = new int[n + 1];

        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
        for (int i = 4; i <= n; i++){
            d[i] = (d[i-1] + d[i-2]) % 1000000007 +d[i-3];
            d[i] %= 1000000007;
        }
        return d[n];
    }

    public static void main(String[] args) {
        System.out.println(waysToStep(61));
    }
}
